class LNode:
    def __init__(self, data=None):
        """
        链表节点类的构造函数
        :param data: 节点的数据域内容，默认为None
        """
        self.data = data  # 结点的数据域
        self.next = None  # 结点的指针域

    def __str__(self):
        """
        重写__str__方法，返回节点数据域数据的字符串表示形式
        :return: 节点数据域数据的字符串表示
        """
        return str(self.data)


class LinkList:
    def __init__(self):
        """
        链表类的构造函数，创建头节点并初始化，头指针head指向头节点
        """
        self.head = LNode(None)  # 生成新结点作为头结点并初始化指针域和数据区域为None，头指针head指向头结点

    def __iter__(self):
        """
        使链表对象可迭代，方便遍历链表中的每个节点
        :return: 生成器，逐个产出链表中的节点
        """
        p = self.head
        while p is not None:
            yield p
            p = p.next

    def __str__(self):
        """
        将链表对象转换为便于阅读的字符串表示形式，用箭头连接各节点数据域内容
        :return: 表示链表结构的字符串
        """
        output = ''
        for idx, item in enumerate(self):
            output += '{arrow}{data}'.format(arrow=' --> ' if idx else '', data=item.data)
        return output

    def __len__(self):
        """
        计算链表的长度（包含头节点在内的所有节点数量）
        :return: 链表的节点个数
        """
        cnt = 0
        for p in self:
            cnt += 1
        return cnt

    def get_elem(self, i):
        """
        在带头结点的单链表中根据序号i获取元素的值
        :param i: 要获取元素的序号
        :return: 对应序号位置节点的数据域内容，如果位置不合法则抛出异常
        """
        for idx, item in enumerate(self):  # 遍历链表
            if idx == i:  # 当下标等于i时，返回该数据元素
                return item.data
        raise Exception('位置不合法')

    def locate_elem(self, e):
        """
        单链表的按值查找，查找成功返回第一个符合的元素，查找失败返回None
        :param e: 要查找的值
        :return: 数据域内容等于e的节点对象，如果未找到则返回None
        """
        for p in self:  # 遍历当前链表
            if p.data == e:
                return p  # 当p的值等于e, 返回p
        return None  # 未找到返回None

    def list_insert(self, i, e):
        """
        在带头结点的单链表中第i个位置插入值为e的新结点
        :param i: 插入位置的序号
        :param e: 要插入的新节点的数据域内容
        :return: 无返回值，如果位置不合法则抛出异常
        """
        for idx, p in enumerate(self):  # 遍历链表
            if idx + 1 == i:
                s = LNode(e)  # 生成新结点s并将s的数据域设置为e
                s.next = p.next  # 将结点s的指针域指向结点ai
                p.next = s  # 将结点p的指针域指向结点s
                return
        raise Exception('位置不合法')

    def list_delete(self, i):
        """
        删除单链表中的第i个结点
        :param i: 要删除节点的序号
        :return: 无返回值，如果位置不合法则抛出异常
        """
        for idx, p in enumerate(self):  # 查找第i - 1个结点，p指向该结点
            if idx + 1 == i and p.next is not None:
                p.next = p.next.next  # 改变删除结点前驱结点的指针域
                return
        raise Exception('位置不合法')

    def create_list_h(self, l_data: list):
        """
        前插法，根据l_data数据列表创建链表，创建的链表数据顺序与输入数据顺序相反
        :param l_data: 包含节点数据的列表
        :return: 无返回值，创建好的链表可通过对象本身访问
        """
        for data in l_data:
            p = LNode(data)  # 生成新结点p，并将p结点的数据域赋值为data
            p.next = self.head.next  # 将新结点p插入到头结点之后
            self.head.next = p

    def create_list_r(self, l_data: list):
        """
        后插法，根据l_data数据列表创建链表，创建的链表数据顺序与输入数据顺序一致
        :param l_data: 包含节点数据的列表
        :return: 无返回值，创建好的链表可通过对象本身访问
        """
        r = self.head  # 尾指针r指向头结点
        for data in l_data:
            p = LNode(data)  # 生成新结点，并初始化p的数据域为data
            r.next = p  # 将新结点p插入尾结点r之后
            r = r.next  # r指向新的尾结点p

    def create_polyn(self, d: list):
        """
        输入多项式的各项系数和指数，建立表示多项式的有序链表l
        :param d: 包含多项式各项系数和指数的字典列表，每个字典有'coef'（系数）和'expn'（指数）两个键
        :return: 创建好的表示多项式的链表对象
        """
        l = LinkList()
        for data in d:  # 遍历各项系数和指数
            s = LNode(data)  # 生成新结点
            pre = l.head  # pre用于保存q的前驱，初值为头结点
            q = pre.next  # q初始化，指向首元结点
            while q is not None and q.data['expn'] < data['expn']:
                # 通过比较指数找到第一个大于输入项指数的项q
                pre = q
                q = q.next
            s.next = q
            pre.next = s  # 将输入项s插入到q和其前驱结点pre之间
        return l

    def add_polyn(self, pa, pb):
        """
        多项式加法：实现pa = pa + pb，利用两个多项式的结点构成“和多项式”
        :param pa: 表示第一个多项式的链表
        :param pb: 表示第二个多项式的链表
        :return: 相加后的多项式链表（结果保存在pa中返回）
        """
        p1, p2 = pa.head.next, pb.head.next  # p1和p2初值分别指向pa和pb的首元结点
        p3 = pa.head  # p3指向和多项式的当前结点

        while p1 is not None and p2 is not None:  # p1和p2均不为None
            if p1.data['expn'] == p2.data['expn']:  # 指数相等
                s = p1.data['coef'] + p2.data['coef']  # s保存两项的系数和
                if s!= 0:  # 系数和不为0
                    p1.data['coef'] = s  # 修改Pa当前结点的系数值为两项系数的和
                    p3.next = p1  # 将修改后的Pa当前结点链在p3之后
                    p3 = p1  # p3指向p1
                p1 = p1.next  # p1指向后一项
                p2 = p2.next  # p2指向后一项
            elif p1.data['expn'] < p2.data['expn']:  # p1当前结点的指数值小
                p3.next = p1  # 将p1链在p3之后
                p3 = p1  # p3指向p1
                p1 = p1.next  # p1指向后一项
            else:  # p2当前结点的指数值小
                p3.next = p2  # 将p2链在p3之后
                p3 = p2  # p3指向p2
                p2 = p2.next  # p2指向后一项

        p3.next = p1 if p1 is not None else p2  # 插入非空多项式的剩余段
        return pa


if __name__ == "__main__":
    data_a = [{'coef': 7.0, 'expn': 0.0}, {'coef': 3.0, 'expn': 1.0}, {'coef': 9.0, 'expn': 8.0},
              {'coef': 5.0, 'expn': 17.0}]
    a = LinkList().create_polyn(data_a)
    print('存储该多项式a的链表为：', a)

    data_b = [{'coef': 8.0, 'expn': 1.0}, {'coef': 22.0, 'expn': 7.0}, {'coef': -9.0, 'expn': 8.0}]
    b = LinkList().create_polyn(data_b)
    print('存储该多项式b的链表为：', b)

    pc = LinkList().add_polyn(a, b)
    print('多项式a与b的和为：', pc)